package com.skh.array;


import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * 两数之和
 * created by skh on 2018/8/18
 */
public class TwoSum {

	/*
	给定一个整数数组和一个目标值，找出数组中和为目标值的两个数。

	你可以假设每个输入只对应一种答案，且同样的元素不能被重复利用。

	示例:

	给定 nums = [2, 7, 11, 15], target = 9

	因为 nums[0] + nums[1] = 2 + 7 = 9
	所以返回 [0, 1]
	 */


	/*
	思路1：
先确定两数中的一个数，再去确定另外一个数，然后判断两数之和与Target的关系。
该解法需要两层for循环，第一个for循环用于确定第一个数，第二个for循环用于确定第二个数，然后在最内部做逻辑判断。
虽然此法简单，但是时间复杂度是O(n2)。显然不是最优解法。
	 */
	public int[] twoSum(int[] nums, int target) {
		int[] result = new int[2];
		for (int i = 0; i < nums.length - 1; i++) {
			for (int j = i + 1; j < nums.length; j++) {
				if (nums[i] + nums[j] == target) {
					result[0] = i;
					result[1] = j;
				}
			}
		}

		return result;
	}

	/*
我们可以在Map中将当前数与Target值得差值作为Key，将当前数的索引作为Value。这样就同时表示了两个维度的信息，Key代表我们对另外一个数的要求，Value代表当前数的索引。
举个例子，Target为9，当前索引为0数为2，那么差值为7。只要后面数组中存在数值为7，那么两者和就为Target。
该思路的核心在于如何在一次操作中确定两个数的信息。这样遍历一遍就能得到结果，其时间复杂度为O(n)。
	 */
	public int[] twoSum2(int[] nums, int target) {
		int[] rs = new int[2];
		Map<Integer, Integer> map = new HashMap();
		for (int i = 0; i < nums.length; i++) {
			if (map.containsKey(nums[i])) {
				rs[0] = map.get(nums[i]);
				rs[1] = i;
				return rs;
			} else {
				map.put(target - nums[i], i);
			}
		}
		return rs;
	}



}
